#include <iostream>
#include <cstdlib>
#include <locale>

static const unsigned short MaxVertexNum = 100;

struct MGraph
{
    char vexs[MaxVertexNum];               // 顶点表的最小规模
    int edges[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
    int n, e;                              // 顶点个数和边数
};

// 建立邻接矩阵
void GreatMGraph(MGraph* G)
{
    int i, j, k;
    char a;
    std::cout << "输入顶点个数VertexNum(n)和边数EdgesNum(e):";
    std::cin >> G->n >> G->e;

    // 这是啥?
    std::cout << " string input" << std::endl;


    for (int i = 0; i < G->n; i++) {
        std::cin >> a; // 这是顶点名称吧？
        G->vexs[i] = a; // 读入顶点信息
    }

    // 给邻接矩阵对角线上的元素赋值为0
    // 因为自己不可能到自己
    for (i = 0; i < G->n; i++)
    {
        for (j = 0; j < G->n; j++)
        {
            G->edges[i][j] = 0;
        }
    }

    std::cout << "输入边的顶点序号:";
    // 输入e条边，建立邻接矩阵
    for (k = 0; k < G->e; k++)
    {
        std::cin >> i >> j;
        // 相互连通的节点
        // ij相连通
        G->edges[i][j] = 1;
        G->edges[j][i] = 1;
    }
}

// 定义标志向量（这是个啥东西）
typedef enum
{
    FALSE,
    TRUE
} Boolean;
Boolean visited[MaxVertexNum];

// DFS
void DFSM(MGraph* G, int i)
{
    // 以Vi为出发点，对图进行DFS
    int j;
    // 顶点i
    std::cout << G->vexs[i];
    // 表示该节点已访问
    visited[i] = TRUE;

    for (j = 0; j < G->n; j++)
    {
        // 该节点必须可连通，并且还没访问过
        if (G->edges[i][j] == 1 && !visited[j])
        {
            // 递归调用，新的节点为j
            DFSM(G, j);
        }
    }
}

void DFS(MGraph* G)
{
    int i;
    for (i = 0; i < G->n; i++)
    {
        visited[i] = FALSE; // 标志向量初始化（保证所有节点都能再次访问）
    }
    for (i = 0; i < G->n; i++)
    {
        if (!visited[i])
        {               // Vi未访问过
            DFSM(G, i); // 以Vi为源点DFS
        }
    }
}

// BFS
void BFS(MGraph* G, int k)
{
    // 以Vk为源点对用邻接矩阵表示的图G进行BFS
    int i, j, f = 0, r = 0;
    int cq[MaxVertexNum]; // 定义队列
    for (i = 0; i < G->n; i++)
    {
        visited[i] = FALSE; // 再次初始化
    }
    for (i = 0; i < G->n; i++)
    {
        cq[i] = -1; // 队列初始化（这是啥）
    }
    std::cout << G->vexs[i]; // 访问源点Vk
    visited[k] = TRUE;
    cq[r] = k; // r、k都还不清楚是什么
    while (cq[f] != -1)
    {
        i = cq[f];
        f += 1;
        // 这个循环也没看懂
        for (j = 0; j < G->n; j++)
        {
            // Vj还未访问
            if (G->edges[i][j] == 1 && !visited[j])
            {
                // 访问Vj
                std::cout << G->vexs[j];
                visited[j] = TRUE;
                r += 1;
                cq[r] = j; // Vj入队
            }
        }
    }
}

int main()
{
    // 这个i没用啊
    // int i;

    MGraph* G;
    G = (MGraph*)malloc(sizeof(MGraph)); // 申请空间
    GreatMGraph(G);
    std::cout << "DFS:" << std::endl;
    DFS(G);

    std::cout << '\n';

    std::cout << "BFS:";
    
    std::cout << std::endl;
    
    BFS(G, 3); // 从3开始广度遍历
    std::cout << std::endl;
}